Network processors are designed for efficient implementation of switching and routing functions. The critical performance measurement for Network processors is the number of machine cycles required to process a typical packet or data frame. This processing is typically broken down into two major parts: the instructions executed by the Network processor CPU (central processing unit), and the access of routing and control tables which are typically stored in a memory source which is shared among several Network processor CPUs. CPU instruction execution is typically stalled during access to the routing tables, adding significantly to the number of machine cycles required to process a packet. In fact, the time to complete an access to one of these tree structures may be 2 or 3 times longer than the time required by the CPU to set up for the access and process the resulting data. The data for these routing and control tables is typically formatted in a tree structure which requires a specialized coprocessor or tree-search engine (TSE) to efficiently access the desired table entry. Other coprocessors, set up to work with data in local data storage, may also stall the CPU, but for shorter durations.
The related art reveals a number of previously patented implementation systems using multiple threads:                U.S. Pat. No. 5,357,617 (Davis, et al.)—This patent deals with switching from one execution thread to another with zero overhead. More specifically, the CPU continuously switches between multiple instruction threads in a time-division multiplexed allocation of CPU resources. In other words, the multiple instruction threads are controlled via a static interleaving mechanism.        U.S. Pat. No. 5,404,469—This patent extends the concept of time-division multiplexed allocation of CPU resources to a processor with a VLIW (very long instruction word) architecture.        U.S. Pat. No. 5,694,604—This patent describes a typical software multiprocessing approach in which a selected instruction thread is allocated a specified amount of time to execute, after which its context is saved, and a previous context for the next instruction thread is restored. In this type of system, each thread typically executes for an extended period of time since there is significant cost (in machine cycles) to save and restore machine context when switching from one thread to another.        U.S. Pat. No. 5,812,811—This patent refers to running multiple instruction threads in parallel which are part of the same program, in order to accelerate completion of the program. It also deals with speculative execution of paths which may or may not be required to complete the execution of the program.        U.S. Pat. No. 5,933,627—This patent describes switching to an alternate thread when the CPU is stalled because required data is not found in local cache. The system requires the CPU to explicitly control which thread would gain control of the CPU. This patent also describes multiple threads as pieces of the same program, rather than independent processes.        U.S. Pat. No. 5,694,603—This patent is another description of a typical software multiprocessing approach which includes preemptive switching from one thread to another.        